/* 小和问题
在一个数组中，每一个数左边比当前数笑的数累加起来，叫做小和
[1,3,4,2,5]
1左边比1小: 没有
3左边比3小: 1
4左边比4小: 1,3
....
小和为16

逆序对： 左边的数如果比右边的数大， 则是逆序对
 */

function smallSum (arr) {
  if (arr == null || arr.length < 2) {
    return
  }
  return mergeSort(arr, 0, arr.length - 1)
}

function mergeSort (arr, l, r) {
  if (l === r) {
    return 0
  }
  const mid = l + Math.floor((r - l) / 2)
  return mergeSort(arr, l, mid) + mergeSort(arr, mid + 1, r) + _merge(arr, l, mid, r)
}

function _merge (arr, l, m, r) {
  const helper = new Array(r - l + 1)
  let i = l
  let j = m + 1
  let index = i - l
  let result = 0
  while (i <= m && j <= r) {
    result += arr[i] < arr[j] ? (r - j + 1) * arr[i] : 0
    // 求逆序对
    if (arr[i] > arr[j]) {
      let tempIndex = i
      while (tempIndex <= m) {
        console.log(`逆序对: ${arr[tempIndex++]}, ${arr[j]}`)
      }
    }
    helper[index++] = arr[i] < arr[j] ? arr[i++] : arr[j++]
  }
  while (i <= m) {
    helper[index++] = arr[i++]
  }
  while (j <= r) {
    helper[index++] = arr[j++]
  }
  for (let i = 0; i < helper.length; i++) {
    arr[l + r] = helper[i]
  }
  return result
}

console.log(smallSum([1, 3, 4, 2, 5]))
